package com.lie.prepare.algorithm.sort;

import java.util.Arrays;

import static com.lie.prepare.util.Print.*;
/**
 * Created by lie on 2018/4/12.
 * 冒泡排序
 * 时间复杂度，O(n^2)
 */
public class BubbleSort {

    public static int[] sort(int[] array){

        int boundEnd = array.length - 2;

        for (int bound = boundEnd;bound>=0;bound--){
            for (int start =0 ;start<=bound;start++){
                if (array[start] > array[start+1]){//注意到这里是start+1，所以boundEnd就要是-2，不然就越界了
                    swap(array, start);
                }
            }
        }

        return array;
    }

    //假如有一趟没有任何交换，则说明排序已经结束
    //可以不用继续下一次外循环了
    public static int[] sortWithStop(int[] array){

        int boundEnd = array.length - 2;

        boolean needStop ;
        for (int bound = boundEnd;bound>=0;bound--){

            needStop = true;

            for (int start =0 ;start<=bound;start++){
                if (array[start] > array[start+1]){//注意到这里是start+1，所以boundEnd就要是-2，不然就越界了
                    swap(array, start);
                    print("触发交换");
                    print(Arrays.toString(array));
                    needStop = false;
                }
            }

            if (needStop) {
                print("-----没有交换");
                //这个时候可以退出外循环了，因为已经排好序了
                print(Arrays.toString(array));
                print("-----跳出循环");
                break;
            }
        }

        return array;
    }

    static void swap(int[] array, int start) {
        int temp = array[start + 1];
        array[start +1] = array[start];
        array[start] = temp;
    }


    public static void main(String[] args){
        int[] array = {1,-1,4, 99, 0, 2, 5, 7};
//        int[] sort = sort(array);
        int[] sort = sortWithStop(array);

        print(Arrays.toString(sort));
    }

}
